package com.test.daily.leetcode.y2022.m06.day0604.v01;

import java.util.*;

/**
 * @descriptions: DirectGraphNode
 * @author: Tom
 * @date: 2022/6/4 下午 08:33
 * @version: 1.0
 */
public class Code03_TopologicalOrderDFS1 {
    // DirectedGraphNode
    public static class DirectedGraphNode {
        public int label;
        public ArrayList<DirectedGraphNode> neighbors;

        public DirectedGraphNode(int label) {
            this.label = label;
            neighbors = new ArrayList<>();
        }

        public static class Record {
            int deep;
            public DirectedGraphNode node;

            public Record(DirectedGraphNode node, int deep) {
                this.deep = deep;
                this.node = node;
            }
        }

        public static class MyComparator implements Comparator<Record> {

            @Override
            public int compare(Record o1, Record o2) {
                return o2.deep - o1.deep;
            }
        }

        public static ArrayList<DirectedGraphNode> topologicalOrder(ArrayList<DirectedGraphNode> graph) {
            HashMap<DirectedGraphNode, Record> order = new HashMap<>();
            for (DirectedGraphNode cur : graph) {
                f(cur, order);
            }
            ArrayList<Record> arrRecord = new ArrayList<>();
            for (Record record : order.values()) {
                arrRecord.add(record);
            }
            arrRecord.sort(new MyComparator());
            ArrayList<DirectedGraphNode> ans = new ArrayList<>();
            for (Record record : arrRecord
            ) {
                ans.add(record.node);
            }
            return ans;
        }

        public static Record f(DirectedGraphNode node, HashMap<DirectedGraphNode, Record> order) {
            if (order.containsKey(node)) {
                return order.get(node);
            }

            int follow = 0;
            for (DirectedGraphNode cur : node.neighbors) {
                follow = Math.max(follow, f(cur, order).deep);
            }
            follow = follow + 1;
            Record ans = new Record(node, follow);
            order.put(node, ans);
            return ans;
        }
    }
}
